package one;

public class Two {

    // 104. 二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHigh = maxDepth(root.left);
        int rightHigh = maxDepth(root.right);
        return Math.max(leftHigh, rightHigh) + 1;
    }

    //112. 路径总和 深度优先遍历
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return targetSum == root.val;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }

    // 121. 买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        int minPries = prices[0], result = 0;
        for (int i = 1; i < prices.length; i++) {
            //找到最小的数字
            if (minPries > prices[i]) {
                minPries = prices[i];
                // 当前位置-当前位置之前最小的
            } else if (result < prices[i] - minPries) {
                result = prices[i] - minPries;
            }
        }
        return result;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
